package link_list;

public class CircleSingleLinkListDemo {
    public static void main(String[] args) {
        CircleSingleLinkList cir = new CircleSingleLinkList();
        cir.greatList(5);
        cir.show();
        cir.joseph(1,2);

    }
}
class CircleSingleLinkList{
    private Boy first = null;
    public void greatList(int num) {
        Boy cur = null;
        if(num<1) {
            System.out.println("需要传入大于1的整数");
            return;
        }
        //添加结点
        for(int i = 1; i<=num; i++) {
            Boy boy = new Boy(i);
            if(i==1) {
                first = boy;
                cur = first;
               first.setNext(first);
            }else {
                cur.setNext(boy);
                boy.setNext(first);
                cur = boy;
            }
        }
    }
    //遍历输出环形链表
    public void show() {
        if(first == null) {
            System.out.println("链表为空");
            return;
        }
        Boy cur = first;
        while (true) {
            System.out.println(cur);
            if(cur.getNext() == first) {
                break;
            }
            cur = cur.getNext();
        }
    }
    //得到环形链表中结点的个数
    public int total() {
        if(first == null) {
            return 0;
        }
        Boy cur = first;
        int count = 0;
        while (true) {
            count++;
            if(cur.getNext() == first) {
                break;
            }
            cur = cur.getNext();
        }
        return count;
    }

    /**
     * 环形链表用于解决约瑟夫问题
     * @param startNo 从第几个小孩开始数
     * @param countNum 每次数几下
     *
     */
    public void joseph(int startNo ,int countNum) {
        if(first == null|| startNo < 1 || startNo > total() || countNum < 1) {
            System.out.println("输入参数有误或链表为空");
            return;
        }
        Boy cur = first;
        //让cur移动到first后面
        while (true) {
            if(cur.getNext() == first) {
                break;
            }
            cur = cur.getNext();
        }
        //让first和cur移动到开始数数的位置
        for (int i = 0; i < startNo-1 ; i++) {
            first = first.getNext();
            cur = cur.getNext();
        }
        //开始出圈
        while (true) {
            //当cur和first相等时，圈中就剩一个小孩
            if(cur == first) {
                break;
            }
            //找到要出圈的小孩
            for (int i = 0; i < countNum-1; i++) {
                first = first.getNext();
                cur = cur.getNext();
            }
            System.out.printf("出圈的小孩号码是%d\n",first.getNo());
            first = first.getNext();
            cur.setNext(first);
        }
        System.out.printf("圈中还剩的小孩的号码是%d\n",first.getNo());
    }
}
class Boy{
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}
